import math
import random

# A set of utilities for using a map imported from the openstreetmap project
# Written by Shaul Markovitch
# 17/11/2013: added a seed
DEFAULT_DB_FILE = "israel.csv"


DRIVEABLE_HIGHWAYS=['motorway','motorway_link','trunk','trunk_link',
                    'primary','primary_link','secondary','secondary_link',
                    'tertiary','tertiary_link','living_street','residential',
                    'unclassified']


SPEED_RANGES = [
                (80,120),   #'motorway'
                (80,100),   #'motorway_link'
                (70,110),   #'trunk'
                (70,90),    #'trunk_link'
                (60,100),   #'primary'
                (60,80),    # 'primary_link'
                (50,90),    #'secondary'
                (50,70),    # 'secondary_link'
                (40,80),    #'tertiary'
                (40,60),    # 'tertiary_link'
                (20,50),    #'living_street'
                (20,50),    #'residential'
                (30,90)     #'unclassified'
                ]
DEFAULT_HIGHWAY_TYPE =    12     #'unclassified'
DEFAULT_MINIMUM_DISTANCE = 50


#CHANGE_PROBABILITY = 0.1
#MAX_NUMBER_OF_CHANGE_EVENTS = 5
#MAX_CHANGE = 0.5
#GLOBAL_CHANGE_PROBABILITY = 0.1

class Link:
    """
    Contains information about a Link from a Junction to another Junction.
    If the road is two-way, there will be a separate Link from the other Junction.
    The target is the key of the taget Junction.
    The distance is in meters.
    The highway type is one of the keys in the SPEED_RANGES list.
    """
    def __init__(self, source,target, distance, highway_type = None, speed = None):
        self.source = source
        self.target = target
        self.distance = distance
        #self.name = name
        if highway_type == None:
            self.highway_type = DEFAULT_HIGHWAY_TYPE
        else:   
            self.highway_type = highway_type
        if speed == None:
            self.speed = self.DefaultSpeed(self.highway_type)
        else:
            self.speed = speed
            
    def DefaultSpeed(self,type_):
        limits = SPEED_RANGES[type_]
        return (limits[0]+limits[1])/2


            
class Junction: 
    """
    Contains information about a single Junction.  The latitude and
    longitude, the type,
    and the list of links to other junctions
    """ 
    def __init__(self,lat,lon,links=[]):
        self.lat = lat
        self.lon = lon
        #self.name = name
        #self.junction_type = junction_type
        self.links = links
        
        


class CountryMap:
    """
    The main class.  All the information is stored in the self.junctions
    dictionary, which contains the set of all Junction instances, hashed by their keys.
    The keys are the ids (integers interpreted as strings) given in the openstreetmap
    db to allow debugging.
    """
    def __init__(self):
        self.junctions = []
        self.speed_ranges = SPEED_RANGES
        self.minimum_distance_for_problem = DEFAULT_MINIMUM_DISTANCE
    
    def GetJunction(self,junction_key):
        return self.junctions[junction_key]
                
        
    def ComputeDistance(self,lat1, long1, lat2, long2):
        """
        The code for the ComputeDistance function was borrowed from 
        http://www.johndcook.com/python_longitude_latitude.html
        distance is in KM
        """
        if (lat1 == lat2 and long1 == long2):
            return 0.0
        if max(abs(lat1-lat2),abs(long1-long2)) < 0.00001:
            return 0.001
                
        # Convert latitude and longitude to 
        # spherical coordinates in radians.
        degrees_to_radians = math.pi/180.0
        # phi = 90 - latitude
        phi1 = (90.0 - lat1)*degrees_to_radians
        phi2 = (90.0 - lat2)*degrees_to_radians
        #
        # theta = longitude
        theta1 = long1*degrees_to_radians
        theta2 = long2*degrees_to_radians
        #
        # Compute spherical distance from spherical coordinates.
        # 
        # For two locations in spherical coordinates 
        # (1, theta, phi) and (1, theta, phi)
        # cosine( arc length ) = 
        #    sin phi sin phi' cos(theta-theta') + cos phi cos phi'
        # distance = rho * arc length
        #
        cos = (math.sin(phi1)*math.sin(phi2)*math.cos(theta1 - theta2) + 
               math.cos(phi1)*math.cos(phi2))
        arc = math.acos( cos )
        #
        # Remember to multiply arc by the radius of the earth 
        # in your favorite set of units to get length.
        return arc * 6373

    def JunctionDistance(self,j1_key,j2_key):
        j1 = self.GetJunction(j1_key)
        j2 = self.GetJunction(j2_key)
        return self.ComputeDistance(j1.lat,j1.lon,j2.lat,j2.lon)
            
    def GenerateProblem(self):
        l = len(self.junctions)
        return [random.randrange(0,l),random.randrange(0,l)]

    
    def LoadMap(self,filename=DEFAULT_DB_FILE):
        for line in open(filename):
                junc = line.strip().split(",")
                junc[0] = float(junc[0])
                junc[1] = float(junc[1])
                j = Junction(junc[0],junc[1])
                raw_links = junc[2].split("#")
                if raw_links == ['']:
                        raw_links = []
                        #print links
                interpreted_links = [[int(i) for i in l.split("@")] for l in raw_links]
                j.links = [Link(len(self.junctions),l[0],l[1],l[2]) for l in interpreted_links]
                self.junctions.append(j)
        self.GenerateRandomTraficReport()
        self.MapStat()		
          
    def GenerateRandomTraficReport(self):
        """
        Simulates trafic reports (Waze style).  Each Link is assigned
        a speed generated randomly uniformly over the range of speeds
        associated with the particular road type.
        """
        random.seed(0)
        for j in self.junctions:
            for l in j.links:
                limits = self.speed_ranges[l.highway_type]
                l.speed = random.randrange(limits[0],limits[1]+1)
        # reset seed to time to allow randomness
        random.seed()

    def MapStat(self):
        print "Number of junctions: %d" % (self._GetNumOfJunctions())
        print "Total links: %d" % (self._GetTotalLinks())
        print "Max branch factor: %d" % (self._GetMaxBranching())
        print "Average branching factor: %g" %(self._GetAvgBranching())
        print "Max distance: %d" % (self._GetMaxDistance())
        print "Min distance: %d" % (self._GetMinDistance())
        print "Average distance: %g" % (self._GetAvgDistance())
        print "Max speed: %d" %(self._GetMaxSpeed())
        print "Min speed: %d" %(self._GetMinSpeed())
        print "Average speed: %g" %(self._GetAvgSpeed())
        for k in range(len(DRIVEABLE_HIGHWAYS)):
            print  DRIVEABLE_HIGHWAYS[k], " :%d" %(self._GetTotalLinksOfType(k))

    def _GetNumOfJunctions(self):
        '''You need to return the total number of junctions '''
        def prepare():
            from numpy import array
            from itertools import chain
            from collections import Counter
            from our_utils import Acc, gamma
            self.speed, self.distance = Acc('speed'), Acc('distance')
            self.t = Counter()
            for i in chain.from_iterable(j.links for j in self.junctions):
                self.distance.add(i)
                self.speed.add(i)
                self.t[i.highway_type] += 1
            ###
            av_speed = self._GetAvgSpeed()
            av_dist = self._GetAvgDistance()
            gamma.values = array([1.0, av_dist / av_speed, av_dist]) / av_speed
        prepare()
        return len(self.junctions)

    def _GetTotalLinks(self):
        '''You need to return the total number of links '''
        return self.speed.count

    def _GetMaxBranching(self):
        '''You need to return the maximal branching factor in a junction '''
        return max(len(j.links) for j in self.junctions)

    def _GetAvgBranching(self):
        'You need to return the average branching factor in a junction'
        return float(self._GetTotalLinks()) / self._GetNumOfJunctions()

    def _GetMaxDistance(self):
        'You need to return the maximal distance between adjacent junctions'
        return self.distance.max

    def _GetMinDistance(self):
        'You need to return the minimal distance between adjacent junctions'
        return self.distance.min

    def _GetAvgDistance(self):
        'You need to return the average distance between adjacent junctions'
        return self.distance.sum / float(self._GetTotalLinks())

    def _GetMaxSpeed(self):
        '''You need to return the maximal speed over all links '''
        return self.speed.max

    def _GetMinSpeed(self):
        '''You need to return the minimal speed over all links '''
        return self.speed.min

    def _GetAvgSpeed(self):
        '''You need to return the average speed over all links '''
        return self.speed.sum / float(self._GetTotalLinks())

    def _GetTotalLinksOfType(self, k):
        '''You need to return the total links where the highway type is k '''
        return self.t[k]

